<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 最大整除子集 -->
    <script>
      var largestDivisibleSubset = function (nums) {
        const len = nums.length
        // 如果长度为0，直接放回空数组
        if (len == 0) {
          return []
        }
        // 先对nums进行排序，使得小的在前面，大的在后面
        nums.sort((a, b) => a - b)
        // 创建dp数组，dp[i]为以nums[i]为最大数的最大整除数组，所以先将nums[i]放入dp[i]中
        const dp = Array.from({ length: len }, (v, i) => new Array(1).fill(nums[i]))
        // res为最终返回的结果，初始值设为一定有的且长度为1的dp[0]
        let res = dp[0]
        for (let i = 1; i < len; i++) {
          for (let j = 0; j < i; j++) {
            // 对于以nums[j]为最大数的最大整除数组，如果nums[i]可以被nums[j]整除，那么nums[i]便能被dp[j]里每一个数整除
            // 于是dp[i]可以为[...dp[j], nums[i]]，但如果要为最大整除数组，需要dp[j]的长度不小于dp[i]现有的长度
            if (nums[i] % nums[j] == 0 && dp[j].length >= dp[i].length) {
              dp[i] = [...dp[j], nums[i]]
            }
          }
          // 将res设成dp数组里长度最大的整除数组
          if (dp[i].length > res.length) {
            res = dp[i]
          }
        }
        return res
      }
      console.log(largestDivisibleSubset([1, 2, 3]))
    </script>
  </body>
</html>
